package com.chj.chuji.tijie09;

// https://blog.csdn.net/weixin_45671214/article/details/104112472
// https://blog.csdn.net/weixin_46592754/article/details/105137943
public class WordSolitaire {

	public static int init(String s1, String s2)// 预处理
	{
		for (int i = s1.length() - 1; i >= 0; --i)// 从尾部开始，保证满足时就是最小
		{
			int flag = 1;
			for (int j = i; j < s1.length(); ++j)// s1从i搜到尾部，s2从头开始搜一样的长度
			{
				if ((j - i) < s2.length() && s1.charAt(j) != s2.charAt(j - i))
					flag = 0;// flag!=0代表当前两段有不一样，继续搜下一段。
			}
			if (flag == 1) {
				System.out.println(s1 + " : " + s2 + " : " + (s1.length() - i));
				return s1.length() - i;// 搜完后flag == 1，所以这两段一样长，返回长度.
			}
		}
		return 0;
	}

	public static void dfs(int x, int len) {
		ans = Math.max(ans, len);
		for (int i = 0; i < n; ++i) {
			if (vis[i] < 2)// 每个单词最多用两次
			{
				if (dp[x][i] != 0)// 能接上才继续搜索
				{
					vis[i]++;// 用上了才加
					dfs(i, len + s[i].length() - dp[x][i]);
					vis[i]--;// 回溯法
				}
			}
		}
	}

	public static int n = 5;
	public static int[][] dp = new int[6][6];
	public static int[] vis = new int[25];
	public static int ans = 0;// dp[i][j]代表i后接j单词的最小重叠部分
	public static String[] s = new String[25];

	public static void main(String[] args) {
		String[] srd = new String[] { "at", "touch", "cheat", "choose", "tact" };
//		int n = 5;
//		int[][] dp = new int[6][6];
//		int[] vis = new int[25];
//		int ans = 0;// dp[i][j]代表i后接j单词的最小重叠部分
//		String[] s = new String[25];
		for (int i = 0; i < n; ++i) {
			s[i] = srd[i];
		}

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				dp[i][j] = init(s[i], s[j]);// 注意这里也可以后接自己
			}
		}

		char a = 'a';

		for (int i = 0; i < n; ++i) {
			if (s[i].charAt(0) == a) {
				vis[i]++;
				dfs(i, s[i].length());
			}
		}

		System.out.println(ans);
	}
}

//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 1e3+5;
//#define INF INT_MAX
//#define INM INT_MIN
//int n,dp[25][25],vis[25],ans = 0;//dp[i][j]代表i后接j单词的最小重叠部分
//string s[25];
//int init(string s1,string s2)//预处理
//{
//    for(int i=s1.size()-1;i>=0;--i)//从尾部开始，保证满足时就是最小
//    {
//        int flag = 1;
//        for(int j=i;j<s1.size();++j)//s1从i搜到尾部，s2从头开始搜一样的长度
//        {
//            if(s1[j] != s2[j-i]) flag = 0;//flag!=0代表当前两段有不一样，继续搜下一段。
//        }
//        if(flag == 1) return s1.size()-i;//搜完后flag == 1，所以这两段一样长，返回长度.
//    }
//    return 0;
//}
//void dfs(int x,int len)
//{
//    ans = max(ans,len);
//    for(int i=0;i<n;++i)
//    {
//        if(vis[i] < 2)//每个单词最多用两次
//        {
//            if(dp[x][i] != 0)//能接上才继续搜索
//            {
//                vis[i]++;//用上了才加
//                dfs(i,len+s[i].size()-dp[x][i]);
//                vis[i]--;//回溯法
//            }
//        }
//    }
//}
//int main()
//{
//    ios::sync_with_stdio(false);
//    char a;
//    cin >> n;
//    for(int i=0;i<n;++i) cin >> s[i];
//    for(int i=0;i<n;++i)
//        for(int j=0;j<n;++j)
//            dp[i][j] = init(s[i],s[j]);//注意这里也可以后接自己
//    cin >> a;
//    for(int i=0;i<n;++i)
//    {
//        memset(vis,0,sizeof(vis));
//        if(s[i][0] == a)
//        {
//            vis[i]++;
//            dfs(i,s[i].size());
//        }
//    }
//    printf("%d\n",ans);
//}
